import java.util.Arrays;

/**
 * @author LKQ
 * @date 2022/2/23 13:23
 * @description 二分查找 + 排序
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] mat = {{1,1,0,0, 0}, {1, 1,1,1, 0}, {1, 0,0,0, 0}, {1,1,0,0,0}, {1,1,1,1,1}};
        solution.kWeakestRows(mat, 3);
    }
    public int[] kWeakestRows(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        int[][] cnt = new int[m][2];
        for (int i = 0; i < m; i++) {
            cnt[i][1] = i;
            // 二分查找最右端的军人位置
            int l = 0, r = n - 1, pos = -1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (mat[i][mid] == 0) {
                    r = mid - 1;
                } else {
                    pos = mid;
                    l = mid + 1;
                }
            }
            cnt[i][0] = pos + 1;
        }
        Arrays.sort(cnt, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            }else {
                return a[1] - b[1];
            }
        });
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = cnt[i][1];
        }
        return ans;
    }
}
